Codeforces/Codeforces Beta Round #90/C/c.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const long long oo = 1LL<<62;
  28
  29 struct subject {
  30     long long a, b;
  31     int c, idx;
  32     subject(){}
  33     bool operator < (const subject &t) const {
  34         if (c != t.c) return c < t.c;
  35         if (a != t.a) return a < t.a;
  36         return b < t.b;
  37     }
  38 };
  39
  40 int N;
  41 long long K;
  42 vector< subject > subjects;
  43
  44 map< pair<int, pair<int, long long > >, long long > memo;
  45
  46 map< pair<int, pair<int, long long > >, pair<int, long long> > choice;
  47
  48 long long f(int k, int last, long long exercises) {
  49     if (k == N) {
  50         //printf("f(k=%d, last=%d, exercises=%lld) = %lld.\n", k, last, exercises, 0LL);
  51         return 0LL;
  52     }
  53
  54     pair<int, pair<int, long long > > key = make_pair(k,  make_pair(last, exercises));
  55     if (memo.count(key)) return memo[key];
  56
  57
  58     long long ans = -oo;
  59     long long choose_exercises = -1;
  60     int choose_next = -1;
  61
  62     for (int j = last + 1; j < subjects.size(); ++j) {
  63         const subject &cur = subjects[j];
  64         if (last >= 0) {
  65             assert(cur.c >= subjects[last].c);
  66             if (cur.c == subjects[last].c) continue; // must be strictly increasing
  67
  68             long long new_exercises[2];
  69
  70             new_exercises[0] = exercises + K;
  71             new_exercises[1] = exercises * K;
  72
  73             for (int p = 0; p < 2; ++p) {
  74                 if (cur.a <= new_exercises[p] and new_exercises[p] <= cur.b) {
  75                     long long option = f(k + 1, j, new_exercises[p]) + new_exercises[p];
  76                     if (option > ans) {
  77                         ans = option;
  78                         choose_exercises = new_exercises[p];
  79                         choose_next = j;
  80                     }
  81                 }
  82             }
  83
  84         } else { // can choose whatever number of exercises I want
  85             assert(k == 0);
  86             for (long long e = cur.a; e <= cur.b; ++e) {
  87                 long long option = f(k + 1,  j,  e) + e;
  88                 if (option > ans) {
  89                     ans = option;
  90                     choose_exercises = e;
  91                     choose_next = j;
  92                 }
  93             }
  94         }
  95     }
  96
  97     //if (ans < oo) printf("f(k=%d, last=%d, exercises=%lld) = %lld. Next is %d with %lld extra exercises\n", k, last, exercises, ans, choose_next, choose_exercises);
  98     memo[key] = ans;
  99     choice[key] = make_pair(choose_next, choose_exercises);
 100     return ans;
 101 }
 102
 103
 104 int main(){
 105     int m;
 106     while (cin >> N >> m >> K) {
 107         subjects.resize(m);
 108         For(i, 0, m) {
 109             cin >> subjects[i].a >> subjects[i].b >> subjects[i].c;
 110             subjects[i].idx = i;
 111         }
 112         sort(subjects.begin(), subjects.end());
 113         // For(i, 0, m) {
 114         //     printf("Subject %d = (a=%lld, b=%lld, c=%d)\n", i, subjects[i].a, subjects[i].b, subjects[i].c);
 115         // }
 116         memo.clear();
 117         long long ans = f(0, -1, 0);
 118         if (ans < 0) {
 119             cout << "NO" << endl;
 120         } else {
 121             cout << "YES" << endl;
 122
 123             int k = 0, last = -1; long long e = 0;
 124             for (int i = 0; i < N; ++i) {
 125                 pair<int, pair<int, long long > > key = make_pair(k,  make_pair(last, e));
 126                 pair< int, long long > c = choice[key];
 127                 cout << subjects[c.first].idx + 1 << " " << c.second << endl;
 128
 129                 k++;
 130                 last = c.first;
 131                 e = c.second;
 132             }
 133         }
 134     }
 135     return 0;
 136 }